package com.leetcode.algorithm.y22.m08.w2;

import java.util.ArrayList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * 
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
 * 
 * @author jie.deng
 *
 */
class Question0017Solution01 {

	public List<String> letterCombinations(String digits) {
		List<String> result = new ArrayList<>();
		if (digits.length() == 0) {
			return result;
		}
		char[][] digitChars = new char[][] {
			{'a','b','c',' '},// 2
			{'d','e','f',' '},// 3
			{'g','h','i',' '},// 4
			{'j','k','l',' '},// 5
			{'m','n','o',' '},// 6
			{'p','q','r','s'},// 7
			{'t','u','v',' '},// 8
			{'w','x','y','z'} // 9			
		};
		
		char[] path = new char[digits.length()];
		backtracking(digits, digitChars, result, 0, path);
		return result;
	}

	private void backtracking(String digits, char[][] digitChars, List<String> result, int startIdx, char[] path) {
		if (startIdx == digits.length()) {
			result.add(String.valueOf(path));
			return;
		}
		char[] chs = digitChars[(digits.charAt(startIdx) - '0') - 2];
		for (int i = 0; i < chs.length && chs[i] != ' '; i++) {
			path[startIdx] = chs[i];
			backtracking(digits, digitChars, result, startIdx + 1, path);
		}
	}

}